1. Field of the Invention
The present invention relates to wireless devices, such as radio-frequency identification (RFID) tags, and, in particular, to methods of quickly estimating the cardinality of a dynamically-changing set of wireless devices, i.e., the number of devices in the set, without explicitly identifying the individual devices of the set.
2. Description of the Related Art
Radio-Frequency Identification (RFID) tags are being increasingly used in many applications for identification and tracking purposes. While these devices offer many advantages to consumers, business, and government, privacy advocates have expressed genuine fears that RFID tags can be used for tracking purposes beyond their intended application or life-span. For example, if there is an RFID tag attached to every electronic device carried by a user, such as a cell phone, music player, laptop, etc., then identification of these tags could allow anyone controlling a network of RFID readers to track the owner of the devices within the range of any reader in the network. There have been some efforts by the RFID industry to address these fears by using special-purpose hardware to disable tags on consumer products before such products are received by the consumer. However, such efforts have not been fully endorsed by the industry, primarily due to concerns about practicality and costs.
While individual, unique identification of tagged items may not be desirable, it is indeed desirable, in numerous applications, to gather statistics concerning the aggregates of users. For example, RFID-tagged shoes or wristwatches could be used to keep track of how many people visit certain stores in a shopping mall, without individually identifying each tag, and without individually identifying the consumers transporting the tags. Users are more likely to adopt devices having RFID tags if their privacy and anonymity can be assured, and merchants can also benefit by using the aggregate tracking information. In fact, recipients of tracking data in most applications that track customers using RFID tags do not actually require individual users to be identified, except in rare circumstances.
When a tag population changes with time, an RFID reader probes the tag set at different time instants. Between any two such probes, some tags might have left the current set, while other tags might have entered this set. In such situations, the cardinality of the encountered tag set can be estimated using estimates of the total number of tags that: (a) have entered the system between the two probes, (b) have left the system between two probes, (c) stay in the system for the entire period, and (d) have been probed at least once.
In a spatially-diverse tag population, a reader can read only a subset of tags with each probe, e.g., as in the case of probing items on a long shelf or an airplane flying over a field of sensors while trying to obtain an estimate of the number of active sensors in the field. In such cases, tags could be probed using one or multiple readers. However, without explicit tag-identification schemes (which take a long time to resolve), it is difficult to count the number of all tags in the system in a short period of time. This is because, when certain estimation schemes are used independently at two neighboring locations (or at two neighboring readers) with overlapping ranges, there are some tags that may end up reporting twice. Strict separation between the two tag sets over successive readings might not be able to be ensured due to (1) a highly-varying radio environment, (2) hard-to-control physical orientation and distance between the reader(s) and the tags, and (3) a need to keep the identities of the tags anonymous.
More-complex scenarios occur with both spatial and temporal diversity, wherein it is desirable to track the number of tagged objects that have moved from a first location A to a second location B over a time period between a first time t1 and a second time t2. One such example would be a highway-system grid, wherein various statistics on the traffic patterns on the grid are desired, without uniquely identifying each vehicle. Given estimates of the number of objects in two locations (measured over different times t1 and t2), it is desirable to estimate how many of these objects were at location A at time t1 and at location B at time t2, without explicitly identifying the tag set. Similarly, it would be desirable to have schemes that can be used to track how many attendees participate in any given subset of sessions at a conference by using privacy-preserving tagged labels for each attendee.
Therefore, there are many scenarios where there is a need for anonymous tracking of quantities of tagged objects.